package leetcode;

import java.util.Arrays;

/**
 * @program: data_structures_algorithms
 * @description:
 * @author: lld
 * @create: 2020-11-18 20:13
 **/
public class Demo2 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 4, 2, 7, 6, 9, 12, 5, 10, 3};
        int[] leastNumbers = getLeastNumbers(arr, 5);
        System.out.println("前K大元素：" + Arrays.toString(leastNumbers));
        int k = findK(arr, 0, arr.length - 1, 4);
        System.out.println("第k大的元素：" + k);


    }

    /**
     * @Description: 定它的大小n和要找的K(K在1到n之间)，请返回第K大的数
     * @Param: [arr, left, right, k]
     * @return: int
     **/
    public static int findK(int[] arr, int left, int right, int k) {
        if (left <= right) {
            int pivot = partition(arr, left, right);

            if (pivot == k - 1) {
                return arr[pivot];
            } else if (pivot < k - 1) {
                return findK(arr, pivot + 1, right, k);
            } else {
                return findK(arr, left, pivot - 1, k);
            }
        }
        return -1;
    }

    public static int[] getLeastNumbers(int[] arr, int k) {
        if (arr.length <= k) {
            return arr;
        }
        if (k == 0) {
            return new int[k];
        }
        int startIndex = 0;
        int endIndex = arr.length - 1;

        partitionArray(arr, startIndex, endIndex, k);
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    /**
     * @Description: 从小到大排序
     * @Param: [arr, startIndex, endIndex]
     * @return: int
     **/
    private static int partition1(int[] arr, int startIndex, int endIndex) {
// 取第一个位置的元素作为基准元素
        int pivot = arr[startIndex];
        int mark = startIndex;//首先指针指向第一个元素
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < pivot) {//小于基准元素，指针右移，交换指针位和arr[i]的值
                mark++;
                int temp = arr[mark];
                arr[mark] = arr[i];
                arr[i] = temp;
            }
        }
        arr[startIndex] = arr[mark];//交换基准和mark的值
        arr[mark] = pivot;
        return mark;
    }

    /**
     * @Description: 从小到大排序
     * @Param: [arr, startIndex, endIndex]
     * @return: int
     **/
    private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第一个位置的元素作为基准元素
        int pivot = arr[startIndex];
        int mark = startIndex;//首先指针指向第一个元素
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] > pivot) {//大于基准元素，指针右移，交换指针位和arr[i]的值
                mark++;
                int temp = arr[mark];
                arr[mark] = arr[i];
                arr[i] = temp;
            }
        }
        arr[startIndex] = arr[mark];//交换基准和mark的值
        arr[mark] = pivot;
        return mark;
    }

    public static void partitionArray(int[] arr, int startIndex, int endIndex, int k) {
        // 做一次 partition 操作
        int m = partition(arr, startIndex, endIndex);
        // 此时数组前 m 个数，就是最小的 m 个数
        if (k == m) {
            // 正好找到最小的 k(m) 个数
            return;
        } else if (k < m) {
            // 最小的 k 个数一定在前 m 个数中，递归划分
            partitionArray(arr, startIndex, m - 1, k);
        } else {
            // 在右侧数组中寻找最小的 k-m 个数
            partitionArray(arr, m + 1, endIndex, k);
        }
    }
}
